<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>/media/src/Dropbox/TC/SingleRoundMatch/SRM211/SRM211DIV1_500.h.html</title>
<meta name="Generator" content="Vim/7.2">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#ffffff" text="#000000"><font face="monospace">
<font color="#8080ff">//Fri Jun&nbsp;&nbsp;3 08:40:30 CDT 2011</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;vector&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;list&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;map&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;set&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;deque&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;stack&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;bitset&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;algorithm&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;functional&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;numeric&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;utility&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;sstream&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;iostream&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;iomanip&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstdio&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cmath&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstdlib&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstring&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;ctime&gt;</font><br>
<br>
<font color="#ffff00">using</font>&nbsp;<font color="#00ff00">namespace</font>&nbsp;std;<br>
<br>
<font color="#00ff00">int</font>&nbsp;dx[] = {<font color="#ff6060">1</font>, -<font color="#ff6060">1</font>, <font color="#ff6060">0</font>, <font color="#ff6060">0</font>};<br>
<font color="#00ff00">int</font>&nbsp;dy[] = {<font color="#ff6060">0</font>, <font color="#ff6060">0</font>, <font color="#ff6060">1</font>, -<font color="#ff6060">1</font>};<br>
<br>
<font color="#00ff00">class</font>&nbsp;grafixMask {<br>
<font color="#ffff00">public</font>:<br>
&nbsp;&nbsp;&nbsp;&nbsp;vector &lt;<font color="#00ff00">int</font>&gt; sortedAreas(vector &lt;string&gt;);<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">void</font>&nbsp;init(vector&lt;string&gt;);<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;dfs(<font color="#00ff00">int</font>, <font color="#00ff00">int</font>);<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">bool</font>&nbsp;avaiID[<font color="#ff6060">400</font>][<font color="#ff6060">600</font>];<br>
};<br>
<br>
<font color="#00ff00">void</font>&nbsp;grafixMask::init(vector&lt;string&gt; rec){<br>
&nbsp;&nbsp;&nbsp;&nbsp;memset(avaiID, <font color="#ff6060">false</font>, <font color="#ffff00">sizeof</font>(avaiID));<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;M = rec.size();<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;M; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stringstream s(rec[i]);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;x1, y1, x2, y2;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s &gt;&gt; x1 &gt;&gt; y1 &gt;&gt; x2 &gt;&gt; y2;<br>
<font color="#8080ff">//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout &lt;&lt; x1 &lt;&lt; &quot;,&quot; &lt;&lt; y1 &lt;&lt; &quot;,&quot; &lt;&lt; x2 &lt;&lt; &quot;,&quot; &lt;&lt; y2 &lt;&lt; endl;</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;x=x1; x&lt;=x2; x++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;y=y1; y&lt;=y2; y++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;avaiID[x][y] = <font color="#ff6060">true</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
}<br>
<br>
<font color="#00ff00">int</font>&nbsp;grafixMask::dfs(<font color="#00ff00">int</font>&nbsp;x, <font color="#00ff00">int</font>&nbsp;y){<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(avaiID[x][y])<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;<font color="#ff6060">0</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;avaiID[x][y] = <font color="#ff6060">true</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;count = <font color="#ff6060">1</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;<font color="#ff6060">4</font>; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;xx = x + dx[i];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;yy = y + dy[i];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(xx &lt;<font color="#ff6060">0</font>&nbsp;|| xx &gt;= <font color="#ff6060">400</font>&nbsp;|| yy &lt; <font color="#ff6060">0</font>&nbsp;|| yy &gt;= <font color="#ff6060">600</font>) <font color="#ffff00">continue</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count += dfs(xx, yy);<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;count;<br>
}<br>
<br>
vector &lt;<font color="#00ff00">int</font>&gt; grafixMask::sortedAreas(vector &lt;string&gt; rectangles) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;init(rectangles);<br>
&nbsp;&nbsp;&nbsp;&nbsp;vector&lt;<font color="#00ff00">int</font>&gt; res;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;<font color="#ff6060">400</font>; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;j=<font color="#ff6060">0</font>; j&lt;<font color="#ff6060">600</font>; j++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(avaiID[i][j] == <font color="#ff6060">false</font>){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;count = dfs(i, j);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res.push_back(count);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;sort(res.begin(), res.end());<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;res;<br>
}<br>
<br>
<br>
<font color="#8080ff">//Powered by [KawigiEdit] 2.0!;</font><br>
</font></body>
</html>
